﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace CodeTop.复习十月份
{
    public class Solution912
    {
        public int[] SortArray(int[] nums)
        {
            //建堆
            MakeBigHeap(nums);
            int len = nums.Length;

            for (int i = len - 1; i >= 0; i--)
            {
                MySwap(nums, 0, i);

                AdjustBigHeap(nums, 0, i);
            }
            return nums;
        }

        private void MakeBigHeap(int[] nums)
        {
            int len = nums.Length;
            for (int i = len / 2; i >= 0; i--)
            {
                AdjustBigHeap(nums, i, len);
            }
        }

        private void AdjustBigHeap(int[] nums, int i, int len)
        {
            int left = 2 * i + 1;
            int right = 2 * i + 2;

            int bigger = i;
            if (left < len && nums[left] > nums[i])
            {
                bigger = left;
            }

            if (right < len && nums[right] > nums[bigger])
            {
                bigger = right;
            }
            if (bigger != i)
            {
                MySwap(nums, i, bigger);
                AdjustBigHeap(nums, bigger, len);
            }
        }

        private void MySwap(int[] nums, int i, int bigger)
        {
            int temp = nums[i];
            nums[i] = nums[bigger];
            nums[bigger] = temp;
        }
    }
}